package leetcode.editor.cn.q1_300.q150;

/**
 * 好吧，又是抄的答案
 * @author qidi
 * @date 2022-01-19 09:59:23
 */
class Q0152_MaximumProductSubarray {

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int maxProduct(int[] nums) {
            int n = nums.length;
            if (n == 1) return nums[0];

            // i 位置最大的积
            int[] maxF = new int[n];
            // i 位置最小的积
            int[] minF = new int[n];

            System.arraycopy(nums, 0, maxF, 0, n);
            System.arraycopy(nums, 0, minF, 0, n);

            for (int i = 1; i < n; i++) {
                /**
                 * 最大积：
                 * nums[i] 为正数 max = nums[i] * 【i 之前的最大积】
                 * nums[i] 为负数 max = nums[i] * 【i 之前的最小积】
                 *
                 * 最小积同理
                 */
                maxF[i] = Math.max(maxF[i - 1] * nums[i], Math.max(nums[i], minF[i - 1] * nums[i]));
                minF[i] = Math.min(minF[i - 1] * nums[i], Math.min(nums[i], maxF[i - 1] * nums[i]));
            }

            int ans = maxF[0];

            for (int i = 1; i < n; i++) {
                ans = Math.max(ans, maxF[i]);
            }

            return ans;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q0152_MaximumProductSubarray().new Solution();
        System.out.println(solution.maxProduct(new int[]{2, 3, -2, 4}));
        System.out.println(solution.maxProduct(new int[]{-2, 0, -1}));
        System.out.println(solution.maxProduct(new int[]{-1, 0, 3, -2, -4}));
        System.out.println(solution.maxProduct(new int[]{-1, 3, 2, 0, 3, -4}));
    }
}